// 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

// 示例:

// 输入: 13
// 输出: 6 
// 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。


#include <string>

using namespace std;

// 1 2 3 4 5 6 7 8 9 
// 10 11 12 13 14 15 16 17 18 19 20

class Solution {
public:
    int countDigitOne(int n) {
        int res{0};
        for (long long i{1}; i <= n; i *= 10) {
            long long divider = i * 10;
            res += (n / divider) * i + min(max(n % divider - i + 1, 0LL), i);
        }
        return res;
    }
};

// 暴力，转成字符串
// 超时
class Solution {
public:
    int countDigitOne(int n) {
        int res{0};
        for (int i{1}; i <= n; ++i) {
            string str = to_string(i);
            res += count(str.begin(), str.end(), '1');
        }
        return res;
    }
};

#include "../stdc++.h"

// 枚举每一位上的1
class Solution {
public:
    int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
            mulk *= 10;
        }
        return ans;
    }
};